package _1_n_queens

import "strings"

func solveNQueens(n int) [][]string {
	var res [][]string
	board := make([][]string, n)
	for i := 0; i < n; i++ {
		board[i] = make([]string, n)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			board[i][j] = "."
		}
	}

	var helper func(startIndex int)
	helper = func(row int) {
		if row == n {
			tmp := make([]string, n)
			for i := 0; i < n; i++ {
				tmp[i] = strings.Join(board[i], "")
			}
			res = append(res, tmp)
			return
		}

		for i := 0; i < n; i++ {
			if isValid(row, i, board, n) {
				board[row][i] = "Q"
				helper(row + 1) // 是一定要注意: 注意这里是startIndex+1,而不是i+1 在一维的空间里，比如组合中，我们使用i+1来控制只能选当前值以及后面的值 在二维空间里，比如n皇后，树的深度(层数)表示的是行(广度表示列)，每层开始的行数与列没有关系，都是上一行+1
				board[row][i] = "."
			}
		}
	}
	helper(0)
	return res
}

func isValid(row int, col int, board [][]string, n int) bool {
	for i := 0; i < n; i++ {
		if board[i][col] == "Q" {
			return false
		}
	}

	for i := 0; i < n; i++ {
		if board[row][i] == "Q" {
			return false
		}
	}

	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] == "Q" {
			return false
		}
	}

	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if board[i][j] == "Q" {
			return false
		}
	}

	return true
}
